<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /**
     * 输入: s1 = "sea", s2 = "eat"
     * 输出: 231
     * 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
     * 在 "eat" 中删除 "t" 并将 116 加入总和。
     * 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
    */

    var minimumDeleteSum = function (s1, s2) {
      let m = s1.length, n = s2.length
      let memo = new Array(m).fill('.').map(() => new Array(n).fill(-1))

      // 定义：dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最小 ASCII 删除和
      function dp(i, j) {
        let res = 0
        // base case
        if (i === s1.length) {
          // 如果 s1 已经遍历完，则只需要将 s2 剩余的字符的 ASCII 值加起来
          res = s2.slice(j).split('').reduce((sum, cur) => sum + cur.charCodeAt(0), 0)
          return res
        }

        if (j === s2.length) {
          // 如果 s2 已经遍历完，则只需要将 s1 剩余的字符的 ASCII 值加起来
          res = s1.slice(i).split('').reduce((sum, cur) => sum + cur.charCodeAt(0), 0)
          return res
        }

        if (memo[i][j] !== -1) {
          return memo[i][j]
        }

        if (s1[i] === s2[j]) {
          // 如果 s1[i] 和 s2[j] 相等，则不需要删除，只需要将 s1[i] 的 ASCII 值加起来
          memo[i][j] = dp(i+1, j+1)
        } else {
          // 如果 s1[i] 和 s2[j] 不相等，则需要删除 s1[i] 或者 s2[j]，取最小值
          memo[i][j] = Math.min(s1[i].charCodeAt(0) + dp(i+1,j), s2[j].charCodeAt(0) + dp(i, j+1))
        }

        return memo[i][j]
      }

      return dp(0, 0)
    };
    console.log(minimumDeleteSum(s1 = "delete", s2 = "leet"));
  </script>
</body>

</html>